home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / etc / RCS / regex.c,v < prev    next >
Text File  |  1989-05-18  |  9KB  |  455 lines
  1. head     1.3;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 1.3
  10. date     89.05.18.17.12.00;  author rab;  state Exp;
  11. branches ;
  12. next     1.2;
  13.  
  14. 1.2
  15. date     88.08.11.15.52.39;  author brent;  state Exp;
  16. branches ;
  17. next     1.1;
  18.  
  19. 1.1
  20. date     88.07.02.18.05.12;  author ouster;  state Exp;
  21. branches ;
  22. next     ;
  23.  
  24.  
  25. desc
  26. @@
  27.  
  28.  
  29. 1.3
  30. log
  31. @Added forward declarations for static functions.
  32. @
  33. text
  34. @/*
  35.  * Copyright (c) 1980 Regents of the University of California.
  36.  * All rights reserved.  The Berkeley software License Agreement
  37.  * specifies the terms and conditions for redistribution.
  38.  */
  39.  
  40. #if defined(LIBC_SCCS) && !defined(lint)
  41. static char sccsid[] = "@@(#)regex.c    5.2 (Berkeley) 3/9/86";
  42. #endif LIBC_SCCS and not lint
  43.  
  44. /*
  45.  * routines to do regular expression matching
  46.  *
  47.  * Entry points:
  48.  *
  49.  *    re_comp(s)
  50.  *        char *s;
  51.  *     ... returns 0 if the string s was compiled successfully,
  52.  *             a pointer to an error message otherwise.
  53.  *         If passed 0 or a null string returns without changing
  54.  *           the currently compiled re (see note 11 below).
  55.  *
  56.  *    re_exec(s)
  57.  *        char *s;
  58.  *     ... returns 1 if the string s matches the last compiled regular
  59.  *               expression, 
  60.  *             0 if the string s failed to match the last compiled
  61.  *               regular expression, and
  62.  *            -1 if the compiled regular expression was invalid 
  63.  *               (indicating an internal error).
  64.  *
  65.  * The strings passed to both re_comp and re_exec may have trailing or
  66.  * embedded newline characters; they are terminated by nulls.
  67.  *
  68.  * The identity of the author of these routines is lost in antiquity;
  69.  * this is essentially the same as the re code in the original V6 ed.
  70.  *
  71.  * The regular expressions recognized are described below. This description
  72.  * is essentially the same as that for ed.
  73.  *
  74.  *    A regular expression specifies a set of strings of characters.
  75.  *    A member of this set of strings is said to be matched by
  76.  *    the regular expression.  In the following specification for
  77.  *    regular expressions the word `character' means any character but NUL.
  78.  *
  79.  *    1.  Any character except a special character matches itself.
  80.  *        Special characters are the regular expression delimiter plus
  81.  *        \ [ . and sometimes ^ * $.
  82.  *    2.  A . matches any character.
  83.  *    3.  A \ followed by any character except a digit or ( )
  84.  *        matches that character.
  85.  *    4.  A nonempty string s bracketed [s] (or [^s]) matches any
  86.  *        character in (or not in) s. In s, \ has no special meaning,
  87.  *        and ] may only appear as the first letter. A substring 
  88.  *        a-b, with a and b in ascending ASCII order, stands for
  89.  *        the inclusive range of ASCII characters.
  90.  *    5.  A regular expression of form 1-4 followed by * matches a
  91.  *        sequence of 0 or more matches of the regular expression.
  92.  *    6.  A regular expression, x, of form 1-8, bracketed \(x\)
  93.  *        matches what x matches.
  94.  *    7.  A \ followed by a digit n matches a copy of the string that the
  95.  *        bracketed regular expression beginning with the nth \( matched.
  96.  *    8.  A regular expression of form 1-8, x, followed by a regular
  97.  *        expression of form 1-7, y matches a match for x followed by
  98.  *        a match for y, with the x match being as long as possible
  99.  *        while still permitting a y match.
  100.  *    9.  A regular expression of form 1-8 preceded by ^ (or followed
  101.  *        by $), is constrained to matches that begin at the left
  102.  *        (or end at the right) end of a line.
  103.  *    10. A regular expression of form 1-9 picks out the longest among
  104.  *        the leftmost matches in a line.
  105.  *    11. An empty regular expression stands for a copy of the last
  106.  *        regular expression encountered.
  107.  */
  108.  
  109. /*
  110.  * constants for re's
  111.  */
  112. #define    CBRA    1
  113. #define    CCHR    2
  114. #define    CDOT    4
  115. #define    CCL    6
  116. #define    NCCL    8
  117. #define    CDOL    10
  118. #define    CEOF    11
  119. #define    CKET    12
  120. #define    CBACK    18
  121.  
  122. #define    CSTAR    01
  123.  
  124. #define    ESIZE    512
  125. #define    NBRA    9
  126.  
  127. static    int advance();
  128. static    char    expbuf[ESIZE], *braslist[NBRA], *braelist[NBRA];
  129. static    char    circf;
  130.  
  131. /*
  132.  * compile the regular expression argument into a dfa
  133.  */
  134. char *
  135. re_comp(sp)
  136.     register char    *sp;
  137. {
  138.     register int    c;
  139.     register char    *ep = expbuf;
  140.     int    cclcnt, numbra = 0;
  141.     char    *lastep = 0;
  142.     char    bracket[NBRA];
  143.     char    *bracketp = &bracket[0];
  144.     static    char    *retoolong = "Regular expression too long";
  145.  
  146. #define    comerr(msg) {expbuf[0] = 0; numbra = 0; return(msg); }
  147.  
  148.     if (sp == 0 || *sp == '\0') {
  149.         if (*ep == 0)
  150.             return("No previous regular expression");
  151.         return(0);
  152.     }
  153.     if (*sp == '^') {
  154.         circf = 1;
  155.         sp++;
  156.     }
  157.     else
  158.         circf = 0;
  159.     for (;;) {
  160.         if (ep >= &expbuf[ESIZE])
  161.             comerr(retoolong);
  162.         if ((c = *sp++) == '\0') {
  163.             if (bracketp != bracket)
  164.                 comerr("unmatched \\(");
  165.             *ep++ = CEOF;
  166.             *ep++ = 0;
  167.             return(0);
  168.         }
  169.         if (c != '*')
  170.             lastep = ep;
  171.         switch (c) {
  172.  
  173.         case '.':
  174.             *ep++ = CDOT;
  175.             continue;
  176.  
  177.         case '*':
  178.             if (lastep == 0 || *lastep == CBRA || *lastep == CKET)
  179.                 goto defchar;
  180.             *lastep |= CSTAR;
  181.             continue;
  182.  
  183.         case '$':
  184.             if (*sp != '\0')
  185.                 goto defchar;
  186.             *ep++ = CDOL;
  187.             continue;
  188.  
  189.         case '[':
  190.             *ep++ = CCL;
  191.             *ep++ = 0;
  192.             cclcnt = 1;
  193.             if ((c = *sp++) == '^') {
  194.                 c = *sp++;
  195.                 ep[-2] = NCCL;
  196.             }
  197.             do {
  198.                 if (c == '\0')
  199.                     comerr("missing ]");
  200.                 if (c == '-' && ep [-1] != 0) {
  201.                     if ((c = *sp++) == ']') {
  202.                         *ep++ = '-';
  203.                         cclcnt++;
  204.                         break;
  205.                     }
  206.                     while (ep[-1] < c) {
  207.                         *ep = ep[-1] + 1;
  208.                         ep++;
  209.                         cclcnt++;
  210.                         if (ep >= &expbuf[ESIZE])
  211.                             comerr(retoolong);
  212.                     }
  213.                 }
  214.                 *ep++ = c;
  215.                 cclcnt++;
  216.                 if (ep >= &expbuf[ESIZE])
  217.                     comerr(retoolong);
  218.             } while ((c = *sp++) != ']');
  219.             lastep[1] = cclcnt;
  220.             continue;
  221.  
  222.         case '\\':
  223.             if ((c = *sp++) == '(') {
  224.                 if (numbra >= NBRA)
  225.                     comerr("too many \\(\\) pairs");
  226.                 *bracketp++ = numbra;
  227.                 *ep++ = CBRA;
  228.                 *ep++ = numbra++;
  229.                 continue;
  230.             }
  231.             if (c == ')') {
  232.                 if (bracketp <= bracket)
  233.                     comerr("unmatched \\)");
  234.                 *ep++ = CKET;
  235.                 *ep++ = *--bracketp;
  236.                 continue;
  237.             }
  238.             if (c >= '1' && c < ('1' + NBRA)) {
  239.                 *ep++ = CBACK;
  240.                 *ep++ = c - '1';
  241.                 continue;
  242.             }
  243.             *ep++ = CCHR;
  244.             *ep++ = c;
  245.             continue;
  246.  
  247.         defchar:
  248.         default:
  249.             *ep++ = CCHR;
  250.             *ep++ = c;
  251.         }
  252.     }
  253. }
  254.  
  255. /* 
  256.  * match the argument string against the compiled re
  257.  */
  258. int
  259. re_exec(p1)
  260.     register char    *p1;
  261. {
  262.     register char    *p2 = expbuf;
  263.     register int    c;
  264.     int    rv;
  265.  
  266.     for (c = 0; c < NBRA; c++) {
  267.         braslist[c] = 0;
  268.         braelist[c] = 0;
  269.     }
  270.     if (circf)
  271.         return((advance(p1, p2)));
  272.     /*
  273.      * fast check for first character
  274.      */
  275.     if (*p2 == CCHR) {
  276.         c = p2[1];
  277.         do {
  278.             if (*p1 != c)
  279.                 continue;
  280.             if (rv = advance(p1, p2))
  281.                 return(rv);
  282.         } while (*p1++);
  283.         return(0);
  284.     }
  285.     /*
  286.      * regular algorithm
  287.      */
  288.     do
  289.         if (rv = advance(p1, p2))
  290.             return(rv);
  291.     while (*p1++);
  292.     return(0);
  293. }
  294.  
  295. /* 
  296.  * try to match the next thing in the dfa
  297.  */
  298. static    int
  299. advance(lp, ep)
  300.     register char    *lp, *ep;
  301. {
  302.     register char    *curlp;
  303.     int    ct, i;
  304.     int    rv;
  305.  
  306.     for (;;)
  307.         switch (*ep++) {
  308.  
  309.         case CCHR:
  310.             if (*ep++ == *lp++)
  311.                 continue;
  312.             return(0);
  313.  
  314.         case CDOT:
  315.             if (*lp++)
  316.                 continue;
  317.             return(0);
  318.  
  319.         case CDOL:
  320.             if (*lp == '\0')
  321.                 continue;
  322.             return(0);
  323.  
  324.         case CEOF:
  325.             return(1);
  326.  
  327.         case CCL:
  328.             if (cclass(ep, *lp++, 1)) {
  329.                 ep += *ep;
  330.                 continue;
  331.             }
  332.             return(0);
  333.  
  334.         case NCCL:
  335.             if (cclass(ep, *lp++, 0)) {
  336.                 ep += *ep;
  337.                 continue;
  338.             }
  339.             return(0);
  340.  
  341.         case CBRA:
  342.             braslist[*ep++] = lp;
  343.             continue;
  344.  
  345.         case CKET:
  346.             braelist[*ep++] = lp;
  347.             continue;
  348.  
  349.         case CBACK:
  350.             if (braelist[i = *ep++] == 0)
  351.                 return(-1);
  352.             if (backref(i, lp)) {
  353.                 lp += braelist[i] - braslist[i];
  354.                 continue;
  355.             }
  356.             return(0);
  357.  
  358.         case CBACK|CSTAR:
  359.             if (braelist[i = *ep++] == 0)
  360.                 return(-1);
  361.             curlp = lp;
  362.             ct = braelist[i] - braslist[i];
  363.             while (backref(i, lp))
  364.                 lp += ct;
  365.             while (lp >= curlp) {
  366.                 if (rv = advance(lp, ep))
  367.                     return(rv);
  368.                 lp -= ct;
  369.             }
  370.             continue;
  371.  
  372.         case CDOT|CSTAR:
  373.             curlp = lp;
  374.             while (*lp++)
  375.                 ;
  376.             goto star;
  377.  
  378.         case CCHR|CSTAR:
  379.             curlp = lp;
  380.             while (*lp++ == *ep)
  381.                 ;
  382.             ep++;
  383.             goto star;
  384.  
  385.         case CCL|CSTAR:
  386.         case NCCL|CSTAR:
  387.             curlp = lp;
  388.             while (cclass(ep, *lp++, ep[-1] == (CCL|CSTAR)))
  389.                 ;
  390.             ep += *ep;
  391.             goto star;
  392.  
  393.         star:
  394.             do {
  395.                 lp--;
  396.                 if (rv = advance(lp, ep))
  397.                     return(rv);
  398.             } while (lp > curlp);
  399.             return(0);
  400.  
  401.         default:
  402.             return(-1);
  403.         }
  404. }
  405.  
  406. backref(i, lp)
  407.     register int    i;
  408.     register char    *lp;
  409. {
  410.     register char    *bp;
  411.  
  412.     bp = braslist[i];
  413.     while (*bp++ == *lp++)
  414.         if (bp >= braelist[i])
  415.             return(1);
  416.     return(0);
  417. }
  418.  
  419. int
  420. cclass(set, c, af)
  421.     register char    *set, c;
  422.     int    af;
  423. {
  424.     register int    n;
  425.  
  426.     if (c == 0)
  427.         return(0);
  428.     n = *set++;
  429.     while (--n)
  430.         if (*set++ == c)
  431.             return(af);
  432.     return(! af);
  433. }
  434. @
  435.  
  436.  
  437. 1.2
  438. log
  439. @Removed annoying '#' that was all alone on a line by itself.
  440. @
  441. text
  442. @d94 1
  443. @
  444.  
  445.  
  446. 1.1
  447. log
  448. @Initial revision
  449. @
  450. text
  451. @a10 2
  452. #
  453.  
  454. @
  455.